//
//  main.cpp
//  数据结构
//
//  Created by 蒋世祺 on 2020/7/4.
//  Copyright © 2020 蒋世祺. All rights reserved.
//

#include <iostream>
using namespace std;

void swap(int &a,int &b){
    
    int temp = a;
    a = b;
    b = temp;
}

/*
直接插入排序（带哨兵）
引入哨兵 从下标为1开始存数
时间：O(n^2)
最坏情况：n(n-1)/2次关键字比较
空间：o(1)
稳定性：稳定
*/
void InsertSort(int * A,int length){
    
    int i,j;
    
    //依次将A2 到 An 插入到前面已经排序的序列
    for(i =2;i<=length;i++){
        
        //若Ai 小于其前驱 将Ai 插入已经排序的序列中
        if(A[i] < A[i-1]){
        
            A[0] = A[i];  //把待插入的值 复制到哨兵
            
            //从后往前与哨兵比较 并且大于哨兵的向后移动
            //直到找到第一个不大于哨兵的值 退出循环
            for(j = i-1;A[0] < A[j];j--){
                
                A[j+1] = A[j];
            }
            
            //即该值应该插入的位置 赋值即可
            A[j+1] = A[0];
        }
    }
}

/*
折半插入排序（带哨兵）
关键字比较的次数减少了 但是移动的元素的次数没有变
时间：O(n^2)
空间：o(1)
稳定性：稳定 （注意折半查找过程）
*/
void Binary_InsertSort(int * A,int length){
    
    int i,j,low,high,mid;
    
    for(i =2;i<=length;i++){
        
        A[0] = A[i];
        
        low = 1;high = i-1;
        
        //折半查找
        while(low<=high){
            
            mid = (low + high)/2;
            
            if(A[mid] > A[0]) high = mid -1;  //查找左半子表
            //这里是没有等于的出口的 这样如果有重复的键值
            //可以一直找到 重复键值最右边的位置插入
            //退出循环时low指向 需要右移的起点下标
            //这个 操作时为了 保证稳定性
            else low = mid +1;  //查找右半子表
        }
        
        //开始右移的起点就是 high+1 或者 low
        for(j = i-1;j>=low;--j)
            A[j+1] = A[j]; //后移空出插入位置
            
        A[low] = A[0];  //插入
    }
}

/*
希尔排序（带哨兵）
对待排序的表 分割成子表进行插入排序 不断缩小排序的步长
时间：优于直接插入排序
空间：O(1)
稳定性：不稳定
适用于：仅适用于顺序表
*/
void ShellSort(int * A,int length){

    int d,i,j;
    
    for(d = length/2;d >= 1;d = d/2){ //步长变化
    
        for(i = d+1;i<=length;i++){ //切换不同的表处理
            
            //下面就是插入排序的过程 只是 加入了步长
            if(A[i]<A[i-d]){
                
                A[0] = A[i];
                
                //按照步长确定同一组中 下一个元素的下标
                for(j = i-d;j>0 && A[0] <A[j];j-=d){
                    
                    A[j+d] = A[j];
                }
                        
                A[j+d] = A[0];
            }
        }
    }
}

/*
冒泡排序
该算法 是从后往前冒泡 每一趟冒泡都会把一个最小值
冒泡到序列的最前面
时间：O(n^2)
最好情况：有序 时间n
最差情况：逆序 时间n^2
空间：O(1)
稳定性：稳定
*/
void BubbleSort(int *A,int length){
    
    //不重复比较已经排序的前面的有序序列
    for(int i =0;i<length-1;i++){
        
        //标记本趟冒泡是否发生交换
        bool flag = false;
        
        //通过j>i 控制不重复比较前面已经排序的
        for(int j = length-1;j>i;j--){
            
            //如果产生逆序 交换位置
            if(A[j-1]>A[j]){
                
                swap(A[j-1],A[j]);
                //完成一次交换就更改标志位
                flag = true;
            }
        }
                
        //如果该趟冒泡 没有逆序对存在
        //说明整体已经排序 终止函数
        if(flag == false){
                
            return;
        }
    }
}

/*
快速排序
选取轴点 分而治之 左边元素全部小于轴点
右边元素全部大于轴点
时间：O(nlog2n) n*递归层数
最好情况：nlog2n 每次划分很平均
最差情况：n^2 逆序或有序
空间：O(递归层数)
最好情况：nlog2n
最差情况：n
稳定性：不稳定
*/
int Partition(int *A,int low,int high){
    
    int pivot = A[low]; //暂时保存轴点的值
    
    //结束时候 low high指向的相同
    //即轴点插入的位置
    while(low < high){
        
        //如果右边high的是大于轴点的就继续左移
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        //如果左边low的是小于轴点的就继续右移
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    
    A[low] = pivot;
    return low;  //返回插入位置
}
void QuickSort(int *A,int low ,int high){

    if(low < high){
         
        //返回low值的插入位置 后面好根据low值分治
        int pivotpos = Partition(&A[0],low,high);
        
        //分治思想的体现
        //按照low值的插入位置分成两半递归下去
        QuickSort(&A[0],low,pivotpos-1);
        QuickSort(&A[0],pivotpos+1,high);
    }
}

/*
简单选择排序
 比较次数的数量级与初始状态无关
 时间：O(n^2)
 空间：O(1)
 稳定性：不稳定
 适用于顺序表和链表
*/
void SelectSort(int * A,int length){
    
    //一共进行n-1躺
    for(int i =0;i<length-1;i++){
         
        int min = i;  //记录最小值的下标
        
        //从左往右遍历比较
        //起点是i+1
        for(int j = i+1;j<length;j++){
            
            //记录该趟 最小值的下标
            if(A[j] <A[min]) min = j;
        }
        
        //如果最小值下标改变了 就交换位置
        if(min != i) swap(A[i],A[min]);
    }
}

/*
堆排序
 从1下标开始存数
 每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换）
 并将待排序元素序列再次调整为大根堆（length--，小元素不断下溢的过程）
 i的左孩子 - 2i
 i的右孩子 - 2i + 1
 i的父亲节点 - i/2
 i所在的层次 - log2（n+1）或者 log2n + 1
 大根堆：完全二叉树中，根 >= 左 和 右
 时间：O(nlog2n)
 空间：O(1)
 稳定性：不稳定
*/
//将以k为根的子树调整为大根堆（下溢操作）时间：O(log2n)
void HeadAdjust(int *A,int k,int length){
    
    A[0] = A[k];  //将这个可能要下溢的节点 始终保持在A[0]这里
    
    //for循环找左孩子节点 不断下溢的过程
    for(int i = 2*k;i<=length;i*=2){
        
        //如果不进去那么最大值就是左节点
        if(i<length && A[i] < A[i+1]){
            
            i++;  //这里i++ 就代表i指向了右节点
        }
        //到这里来i已经指向了k最大的孩子下标
        
        //如果满足 根 >= 左 和 右 直接break 不需要调整
        if(A[0] >= A[i]){
            
            break;
        }else{
            
            A[k] = A[i]; //将最大的子节点 赋值给父亲节点
            k = i;  //替换k的指向 即不是直接交换父子的值 而是A[0]这个点的位置一直属于待定状态 继续进行向下的比较
            //直到break出去 才把A[0]赋值
        }
    }
    
    A[k] = A[0];  //A[0]经过n次下溢的操作后 k最后指向了它该插入的位置
}
//建立大根堆 从下往上的下溢 时间：O(n)
void BuildMaxHeap(int * A,int length){
    
    //从后往前调整所有非根端节点
    for(int i = length/2;i>0;i--){
        
        HeadAdjust(A,i,length);
    }
}
//堆排序完整逻辑 时间：n + nlog2n = O(nlog2n)
void HeapSort(int * A,int length){
    
    //先将数组中元素调整为大根堆形式
    BuildMaxHeap(A,length);
    
    //n-1躺下溢的操作 也就是时间：O(nlog2n)
    for(int i = length;i>1;i--){  //排序好的元素都在后部分 i-- 即不会重复排序
        
        //比i下标大的的部分已经是全部排序的了
        swap(A[i],A[1]);  //此时1指向的是未排序序列的最大值 和i交换
        //i对应元素被交换到了堆顶 所以要进行下溢操作
        //此时传入的length值要减小1 因为 第i个数已经进入了完成排序的序列中
        HeadAdjust(A, 1, i-1);
    }
}
/*
补充：堆的插入删除
 1、插入：（1）新元素放到表尾（堆底）
         （2）根据大小根堆的要求，新元素不断的上溢，直到无法上升为止
 2、删除：（1）被删除元素用表尾元素代替
         （2）根据大小根堆的要求，新元素不断的下溢，直到无法下降为止
 3、关键字对比次数：（1）每次上溢调整只需要对比关键字一次（与父节点关键字对比）
                 （2）每次下溢调整可能需要对比两次（有左右子节点），也可能只需要对比一次（只有左节点）
 */

/*
归并排序
 待排序数据太大时候 多用于外部排序
 比较次数的数量级与初始状态无关
 时间：O(nlog2n)
 空间：O(n)
 稳定性：稳定
*/
int n;  //待排序的序列长度
int *B = (int *)malloc(n*sizeof(int));  //开的辅助空间

//合并两个已经排序的子序列 时间：O(n)
void Merge(int *A,int low,int mid,int high){
    
    int i,j,k;
    
    //把两个待排序的子序列复制到辅助数组中
    for(k = low;k <= high;k++){
        
        B[k] = A[k];
    }
    
    //开始时 i j 分别指向两个子序列的起点位置 所以初始值不同
    //k 指向原序列A中 这两块待合并序列的起始位置
    //k 始终自加 因为不管是哪个子序列放入A中 A下一次的放入位置都得加一
    //跳出条件 i或者j 超过各自的序列长度 也就是其中一个子序列已经全部进入A序列中有序排列了
    for(i = low,j = mid + 1,k = low;i <= mid && j <= high;k++){
        
        if(B[i] <= B[j]){  //这里带等于号保证了该排序算法的稳定性
            
            A[k] = B[i++]; //B的i序列中 第i个元素放入A中 i自加指向下一个元素
        }else{
            
            A[k] = B[j++]; //B的j序列中 第ij个元素放入A中 j自加指向下一个元素
        }
    }//一定是有一个子序列全部进入A了才会跳出for循环
    
    //这时候 有一个子序列剩下的元素直接全部放入A剩余的位置就行了
    while(i <= mid) A[k++] = B[i++];
    while(j <= high) A[k++] = B[j++];
}
//递归执行划分区间的操作（分治思想）
void MergeSort(int *A,int low ,int high){
    
    if(low < high){//推出条件
        
        int mid = (low +high)/2;  //二分区间
        
        //递归执行
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        //把递归的执行操作放在最后也就是后续遍历二叉树的顺序执行操作
        //后续遍历的顺序 才能保证从最小的两个序列开始归并 这样才能保证往后每次归并的 两个大序列已经是有序的
        Merge(A, low, mid, high);  //归并操作会执行 log2n 次
    }
}

/*
基数排序
 基数排序不是基于“比较”的算法
 擅长解决的问题：
  （1）数据元素的关键字（例如：百位数 可以拆分成 个位 十位 百位 所以 d = 3）可以方便的拆分为d组，且d较小；
  （2）毎组关键字的取值范围（例如：十进制树，取值范围就是0～9 所以 r = 10）不大，即r较小；
  （3）数据元素的个数n（数据集合的大小）较大；
 时间：O(d(n+r))
 收集队列的时间：O(1)（链表结构接上一个队列的队头 所以回收时间复杂度是1）
 空间：O(r)
 稳定性：稳定
*/
//基数排序通常基于链式存储实现
typedef struct LinkNode{
    
    int data;
    struct LinkNode *next;
}LinkNode,*LinkList;

//链式队列
typedef struct{
    
    LinkNode *front,*rear;  //队列的队头和队尾元素
}LinkQueue;




int main(){
    
    int A[5] = {5,4,3,2,1};
    
    n = 5;
    MergeSort(&A[0],0,4);
    
    for(int i =0;i<5;i++){
        
        cout << A[i]<<" ";
    }
    
    return 0;
}
